package com.wlr.study.leetcode.lrulfu;

import java.util.HashMap;
import java.util.Map;

public class LruCode {
    /**
     * 虚拟头结点  尾结点
     */
    private DoubleLinkedList head, tail;
    private Map<Integer, DoubleLinkedList> map = new HashMap<>();
    // 容量
    private int capacity;
    //实际元素个数
    private int size;

    /**
     * 数据初始化
     *
     * @param capacity
     */
    public LruCode(int capacity) {
        this.capacity = capacity;
        head = new DoubleLinkedList();
        tail = new DoubleLinkedList();
        head.next = tail;
        tail.pre = head;
        this.map = new HashMap<>();
    }

    /**
     * 对外暴露的get方法
     *
     * @param key key
     * @return
     */
    public int get(int key) {
        // 如果不存在key，则返回-1
        if (!map.containsKey(key)) {
            return -1;
        }
        // 将key给get出来
        DoubleLinkedList node = map.get(key);
        moveToHead(node);
        return node.value;
    }

    /**
     * 对外暴露的put方法
     *
     * @param key
     * @param value
     */
    public void put(int key, int value) {
        // 如果存在该key
        if (map.containsKey(key)) {
            // get出来   替换value值   因为使用过   移动到头结点
            DoubleLinkedList node = map.get(key);
            node.value = value;
            moveToHead(node);
        } else {
            // 因为不存在该key
            // 所以创建新的节点
            DoubleLinkedList newNode = new DoubleLinkedList(key, value);
            map.put(key, newNode);
            addHead(newNode);
            size++;
            // 如果元素总数量大于最大容量  移除最后一个节点，也就是最少使用的节点
            if (size > capacity) {
                removeLastNode();
            }
        }
    }

    /**
     * 删除尾结点
     */
    private void removeLastNode() {
        DoubleLinkedList lastNode = tail.pre;
        removeNode(lastNode);
        map.remove(lastNode.key);
        size--;

    }

    /**
     * 删除节点
     *
     * @param lastNode
     */
    private void removeNode(DoubleLinkedList lastNode) {
        lastNode.next.pre = lastNode.pre;
        lastNode.pre.next = lastNode.next;
        lastNode.next = null;
        lastNode.pre = null;

    }

    /**
     * 添加节点到头结点
     *
     * @param newNode
     */
    private void addHead(DoubleLinkedList newNode) {
        newNode.pre = head;
        newNode.next = head.next;
        head.next.pre = newNode;
        head.next = newNode;
    }

    /**
     * 移动节点到头结点
     *
     * @param node
     */
    private void moveToHead(DoubleLinkedList node) {
        removeNode(node);
        addHead(node);
    }
}
